package com.leetcode.contest;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/7 22:26
 */
public class LC5920分配给商店的最多商品的最小值 {

    public static int minimizedMaximum(int n, int[] quantities) {
        //相关题目：875. 爱吃香蕉的珂珂
        int left = 1, right = Arrays.stream(quantities).max().getAsInt();
        while (left < right) {
            int mid = (left + right) >>> 1;
            //记录以mid进行平方能满足的商店数
            int count = 0;
            //每种物品都以mid为标准进行分配给各个商店，向上取整
            for (int quantity : quantities) {
                count += (quantity - 1) / mid + 1;
            }
            //mid过大，导致满足的商店太少
            if (count <= n) {
                right = mid;
            } else {
                //mid过小，虽然都满足了，但是还剩余很多物品
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int n = 1;
        int[] quantities = {1};
        System.out.println(minimizedMaximum(n, quantities));
    }
}
